/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-09 14:09:14
 * @LastEditors: lily
 * @LastEditTime: 2021-04-15 10:08:38
 */
/*
 * @lc app=leetcode.cn id=31 lang=javascript
 *
 * [31] 下一个排列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

//  思路：
//  满足字典序：1) 比当数大 2) 增幅最小
//  从后往前比 找到第一个升序对(i,j) 交换两者 保证j尽量靠右
//  再将i后的数字进行升序排列，此时(j,end)一定是降序，翻转即可

//  复杂度：O(n)  O(1)

var nextPermutation = function (nums) {
    const len = nums.length
    if (len < 1) return nums
    let pair1, pair2
    for (let i = len - 1; i >= 0; i--) {
        // 先找相邻升序对(i,i+1) 再从i+1开始找j尽量靠右的升序对
        if (nums[i] < nums[i + 1]) {
            pair1 = i
            break
        }
        if (i === 0) {
            // 找不到相邻的升序对
            return nums.reverse()
        }
    }
    // 找到最靠右的j
    for (let j = pair1 + 1; j < len; j++) {
        if (nums[j] > nums[pair1]) {
            pair2 = j
        }
    }

    // 交换pair1 和pair2的值
    [nums[pair1], nums[pair2]] = [nums[pair2], nums[pair1]]

    //  反转 (pair1,end)
    for (let i = pair1 + 1, j = len - 1; i < j; i++, j--) {
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    return nums
};
// @lc code=end

console.log(nextPermutation([1, 2, 3, 8, 5, 7, 6, 4]));